/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  const mergeList = (left, right, arr) => {
    if(left > right) return null
    if(left === right) return arr[left]
    let mid = (left + right + 1) >> 1
    let l1 = mergeList(left, mid, arr)
    let l2 = mergeList(mid + 1, right, arr)
    return merge(l1, l2)
  }
  return mergeList(0, lists.length - 1, lists)
};
function merge(l1, l2) {
  let dummy = new ListNode()
  let pre = dummy
  let p1 = l1, p2 = l2
  while(p1 && p2) {
    if(p1.val < p2.val) {
      pre.next = p1
      p1 = p1.next
    } else {
      pre.next = p2
      p2 = p2.next
    }
    pre = pre.next
  }
  if(p1) pre.next = p1
  if(p2) pre.next = p2
  return dummy.next
}